#ifndef __LNB__
#define __LNB__

#pragma once

#include <string> // std::string
#include <fstream> // std::ifstream
#include <chrono> // std::chrono::high_resolution_clock
#include <map>
#include <set>
#include <tuple>
#include <vector>

#include "geo_defines.h" // R*-tree, EARTH_RADIUS, PI
#include "typed_directed_graph.h"
#include "k_median.h"

//================================================================================
// REMARK:
//	if a candidate locates in a local network of a reference location, which has no nearest facility (namely isolate sub-grahp), we view its ERD as 0


//================================================================================
// testing for output edges in graph

//#define ALGO_TESTING
#define ALGO_TESTING_NO_TRACE_GRAPH
//#define ALGO_TESTING_NO_EARLY_STOPPING // early stopping "ol.ERD > next upper bound" is ignored for testing

// static std::ofstream algo_out_file("D:\\Experiment\\MILE-RUN\\datasets\\algo_testing.txt", std::ofstream::out | std::ofstream::trunc);

void print_graph(const typed_directed_graph& graph);



//================================================================================
// Local Network Table for LNB algorithm;
// an assistant hash map for local network edges, which consists of shortest distances from a reference location to a vertex, and that distance plus out-edge weight (distance)
// an assistant hash map for information of candidates
// an assistant hash map for reference locations that overlap some vertices

typedef boost::unordered_map < std::pair < int, int >, // ids of starting and ending vertices of a directed edge, whose format is <vs_id, ve_id>
	boost::tuple < double, // prob
	double, // dist(r, vs), use DDU for alternative
	double, // dist(r, vs) + dist(vs, ve), use DDL for alternative
	int > > // ve_id, use OFFSET for alternative
loc_edges_hash_map; // assistant hash map

typedef boost::tuple < double, // prob
	double, // Dd+ (Dd upper bound)
	double, // Dd- (Dd lower bound)
	double,// offset
	int>  // r_id
ref_loc_entry;

enum ref_loc_entry_element { PROB = 0, DDU, DDL, OFFSET, REFF }; // OFFSET also represent "ve_id" when for "loc_edges_hash_map", as "VE_ID" has been defined in "fac_hash_map_element"

typedef boost::unordered_map < std::pair < int, int >, // ids of starting and ending vertices of a directed edge, whose format is <vs_id, ve_id>
	std::pair < double, // ERD+ (ERD upper bound on a directed edge)
	std::vector<ref_loc_entry> > >
LNT_hash_map;

typedef boost::unordered_map < int, // candidate id
	boost::tuple < LNT_hash_map::const_iterator, // const iterator pointing to edge "vs_id-ve_id" in LNT
	LNT_hash_map::const_iterator, // const iterator pointing to edge "ve_id-vs_id" in LNT
	double, // dist_vs
	double > > // dist_ve
cand_info_hash_map; // assistant hash map

enum cand_info_hash_map_element { ITER_VS_VE = 0, ITER_VE_VS }; // the value of VS_DIST, VE_DIST are defined and consistent with "fac_hash_map_element"

typedef boost::unordered_map < int, // vertex id
	double > // accumulated nnd
vertex_nnd_hash_map; // assistant hash map

//--------------------------------------------------------------------------------
// top event visitor for LNB algorithm
// remark: if a candidate locates in a local network of a reference location, which has no nearest facility (namely isolate sub-grahp),
//			LNT and vertex_nnd hash maps will never record any local network of the reference location, and we view its ERD as 0

class LNB_top_visitor
	: public top_event_visitor
{
public:
	virtual bool operator()(const target_vertex &v, const definite_hash_map &hash_map)
	{
		if (v.type == 'f') // 找到了最近设施
		{
			double nnd = v.dist; // 最近设施的距离

			if (r_v_id != -1) // 参考位置覆盖了一个端点
			{
#ifdef ALGO_TESTING
				algo_out_file << "r overlaps v" << r_v_id << ", nnd = " << v.dist << '\n';
#endif
				vertex_nnd_hash_map::iterator iter_nnd = ptr_nnd_hash_map->find(r_v_id);
				if (iter_nnd != ptr_nnd_hash_map->end()) // the vertex has been overlapped by some reference location
					iter_nnd->second += nnd; // accumulate nnd
				else // the vertex is overlapped by this reference location first time
					(*ptr_nnd_hash_map)[r_v_id] = nnd; // initial nnd
			}

			// deal with each edge in the local network of a reference location
			// 处理位于该参考位置的本地网络中的每一条边
			loc_edges_hash_map::iterator iter_edge = ptr_loc_edges_hash_map->begin();
			for (; iter_edge != ptr_loc_edges_hash_map->end(); ++iter_edge)
			{
				// for clarity, we define two variables below
				// 为了清晰起见，我们定义了两个变量
				std::pair<int, int> vs_ve = iter_edge->first; // the edge vs->ve, <vs_id, ve_id>
				int ve_id = iter_edge->second.get<OFFSET>(); // use OFFSET for alternative, actually is "ve_id"

				// compute offset
				double offset = 0.0f;
				definite_hash_map::const_iterator iter_definite = hash_map.find(vertex(ve_id, 'v'));
				if (iter_definite != hash_map.cend() // ve has definite shortest path distance d(r, ve)
					&& iter_definite->second < iter_edge->second.get<DDL>()) // d(r, ve) < d(r, vs) + d(vs, ve)
					offset = (iter_edge->second.get<DDL>() - iter_definite->second) / 2.0f; // (d(r, vs) + d(vs, ve) - d(r, ve)) / 2

				// create new entry in LNT
				// 在LNT中创建新的条目
				double Dd_u = nnd - iter_edge->second.get<DDU>(); // Dd+ = nnd - dist(r, vs)
				LNT_hash_map::iterator iter_LNT = ptr_LNT_hash_map->find(vs_ve);
				if (iter_LNT != ptr_LNT_hash_map->end()) // edge "vs_id-ve_id" has already been in local network of other reference locations
				{
					iter_LNT->second.first += (Dd_u * iter_edge->second.get<PROB>()); // new_ERD+ = old_ERD+ + (Dd+ * prob)
					iter_LNT->second.second.push_back(boost::make_tuple(iter_edge->second.get<PROB>(), // prob
						Dd_u, // Dd+
						nnd - iter_edge->second.get<DDL>(), // Dd- = nnd - (dist(r, vs) + dist(vs, ve))
						offset,r_id)); // offset
				}
				else // "vs_id-ve_id" first time presents
				{
					(*ptr_LNT_hash_map)[vs_ve] = std::make_pair(Dd_u, // Dd+ as initial ERD+
						std::vector<ref_loc_entry>());
					(*ptr_LNT_hash_map)[vs_ve].second.push_back(boost::make_tuple(iter_edge->second.get<PROB>(), // prob
						Dd_u, // Dd+
						nnd - iter_edge->second.get<DDL>(), // Dd- = nnd - (dist(r, vs) + dist(vs, ve))
						offset,r_id)); // offset
				}
			}
			return true; // a flag to terminate graph traversal
		}
		return false; // a flat to continue graph traversal
	}

	void set_data_structures(LNT_hash_map *LNT_hash_map_in, loc_edges_hash_map *loc_edges_hash_map_in, vertex_nnd_hash_map *nnd_hash_map)
		{ ptr_LNT_hash_map = LNT_hash_map_in; ptr_loc_edges_hash_map = loc_edges_hash_map_in; ptr_nnd_hash_map = nnd_hash_map; }
	void set_overlap(int r_v_id_in, int id) { r_v_id = r_v_id_in; r_id = id; };

private:
	LNT_hash_map *ptr_LNT_hash_map; // a pointer to a hash map as Local Network Table
	loc_edges_hash_map *ptr_loc_edges_hash_map; // a pointer to an assistant hash map for local network edges
	vertex_nnd_hash_map *ptr_nnd_hash_map; // a pointer to an assistant hash map for reference locations that overlap some vertices
	int r_v_id; // indicate whether this reference location overlaps a vertex (v_id) or not (-1)
	int r_id;
};


class LNB_k_top_visitor
	: public top_event_visitor
{
public:
	virtual bool operator()(const target_vertex &v, const definite_hash_map &hash_map)
	{
		if (v.type == 'f') // 找到了最近设施
		{
			double nnd = v.dist; // 最近设施的距离
			(*ptr_refloc_info)[refloc_id] = std::make_pair(v.id,v.dist);
			if (r_v_id != -1) // 参考位置覆盖了一个端点
			{
#ifdef ALGO_TESTING
				algo_out_file << "r overlaps v" << r_v_id << ", nnd = " << v.dist << '\n';
#endif
				vertex_nnd_hash_map::iterator iter_nnd = ptr_nnd_hash_map->find(r_v_id);
				if (iter_nnd != ptr_nnd_hash_map->end()) // the vertex has been overlapped by some reference location
					iter_nnd->second += nnd; // accumulate nnd
				else // the vertex is overlapped by this reference location first time
					(*ptr_nnd_hash_map)[r_v_id] = nnd; // initial nnd
			}

			// deal with each edge in the local network of a reference location
			// 处理位于该参考位置的本地网络中的每一条边
			loc_edges_hash_map::iterator iter_edge = ptr_loc_edges_hash_map->begin();
			for (; iter_edge != ptr_loc_edges_hash_map->end(); ++iter_edge)
			{
				// for clarity, we define two variables below
				// 为了清晰起见，我们定义了两个变量
				std::pair<int, int> vs_ve = iter_edge->first; // the edge vs->ve, <vs_id, ve_id>
				int ve_id = iter_edge->second.get<OFFSET>(); // use OFFSET for alternative, actually is "ve_id"

				// compute offset
				double offset = 0.0f;
				definite_hash_map::const_iterator iter_definite = hash_map.find(vertex(ve_id, 'v'));
				if (iter_definite != hash_map.cend() // ve has definite shortest path distance d(r, ve)
					&& iter_definite->second < iter_edge->second.get<DDL>()) // d(r, ve) < d(r, vs) + d(vs, ve)
					offset = (iter_edge->second.get<DDL>() - iter_definite->second) / 2.0f; // (d(r, vs) + d(vs, ve) - d(r, ve)) / 2

				// create new entry in LNT
				// 在LNT中创建新的条目
				double Dd_u = nnd - iter_edge->second.get<DDU>(); // Dd+ = nnd - dist(r, vs)
				LNT_hash_map::iterator iter_LNT = ptr_LNT_hash_map->find(vs_ve);
				if (iter_LNT != ptr_LNT_hash_map->end()) // edge "vs_id-ve_id" has already been in local network of other reference locations
				{
					iter_LNT->second.first += (Dd_u * iter_edge->second.get<PROB>()); // new_ERD+ = old_ERD+ + (Dd+ * prob)
					iter_LNT->second.second.push_back(boost::make_tuple(iter_edge->second.get<PROB>(), // prob
						Dd_u, // Dd+
						nnd - iter_edge->second.get<DDL>(), // Dd- = nnd - (dist(r, vs) + dist(vs, ve))
						offset,refloc_id)); // offset
				}
				else // "vs_id-ve_id" first time presents
				{
					(*ptr_LNT_hash_map)[vs_ve] = std::make_pair(Dd_u, // Dd+ as initial ERD+
						std::vector<ref_loc_entry>());
					(*ptr_LNT_hash_map)[vs_ve].second.push_back(boost::make_tuple(iter_edge->second.get<PROB>(), // prob
						Dd_u, // Dd+
						nnd - iter_edge->second.get<DDL>(), // Dd- = nnd - (dist(r, vs) + dist(vs, ve))
						offset,refloc_id)); // offset
				}
				(*ptr_refloc_LN)[refloc_id].insert(vs_ve);
			}
			return true; // a flag to terminate graph traversal
		}
		return false; // a flat to continue graph traversal
	}

	void set_data_structures(LNT_hash_map *LNT_hash_map_in, loc_edges_hash_map *loc_edges_hash_map_in, vertex_nnd_hash_map *nnd_hash_map, std::map<int, std::set<std::pair<int, int>>> * refloc_LN_map, std::map<int,std::pair<int,double>> * refloc_info)
	{
		ptr_LNT_hash_map = LNT_hash_map_in; ptr_loc_edges_hash_map = loc_edges_hash_map_in; ptr_nnd_hash_map = nnd_hash_map;  ptr_refloc_LN = refloc_LN_map;
		ptr_refloc_info = refloc_info;
	}
	void set_overlap(int r_v_id_in) { r_v_id = r_v_id_in; };
	void set_refloc(int r_id, double p)
	{
		refloc_id = r_id; prob = p;
	}

private:
	LNT_hash_map *ptr_LNT_hash_map; // a pointer to a hash map as Local Network Table
	loc_edges_hash_map *ptr_loc_edges_hash_map; // a pointer to an assistant hash map for local network edges
	vertex_nnd_hash_map *ptr_nnd_hash_map; // a pointer to an assistant hash map for reference locations that overlap some vertices
	std::map<int, std::set<std::pair<int, int>>> * ptr_refloc_LN;
	std::map<int,std::pair<int,double>>* ptr_refloc_info;
	double prob;
	int refloc_id;
	int r_v_id; // indicate whether this reference location overlaps a vertex (v_id) or not (-1)
};


//--------------------------------------------------------------------------------
// extend event visitor for LNB algorithm

class LNB_extend_visitor
	: public extend_event_visitor
{
public:
	virtual bool operator()(const target_vertex &v, const out_edge &e) //输入的参数是：当前找到的最近距离的点以及该点的一条出边
	{
		if (v.type != 'r') // 不可能是f，因为如果是f，top_visitor已经检测了，一定是v。impossible to be 'f', then must be 'v'
		{
			if (e.ve.type != 'f') // must be 'v' (e.dist is impossible to be zero), then v->e.ve
			{
				(*ptr_loc_edges_hash_map)[std::pair<int, int>(v.id, e.ve.id)] = boost::make_tuple(prob, v.dist, v.dist + e.dist, e.ve.id);
#ifdef ALGO_TESTING
				algo_out_file << ss_vs_ve.str() << ", d(r,vs) = " << v.dist << ", d(r,vs)+d(vs,ve) = " << v.dist + e.dist << '\n';
#endif
				return false; // a flag to continue graph traversal
			}
			else // e.ve.type == 'f'
			{
				if (e.dist == 0) // f overlaps v, then no need to consider this virtual edge
					return false; // a flag to continue graph traversal
				else // e.dist != 0, e.ve is a facility that must split an edge
				{
					fac_hash_map::iterator iter_fac = ptr_fac_hash_map->find(e.ve.id); // the facility must exist
					if (v.id == iter_fac->second.get<VS_ID>()) // f.vs(v)->f.ve
					{
						(*ptr_loc_edges_hash_map)[std::pair<int, int>(v.id, iter_fac->second.get<VE_ID>())] =
							boost::make_tuple(prob, v.dist, v.dist + iter_fac->second.get<VS_DIST>() + iter_fac->second.get<VE_DIST>(), iter_fac->second.get<VE_ID>());
#ifdef ALGO_TESTING
						algo_out_file << ss_vs_ve.str() << ", d(r,vs) = " << v.dist << ", d(r,vs)+d(vs,ve) = " << v.dist + iter_fac->second.get<VS_DIST>() + iter_fac->second.get<VE_DIST>() << '\n';
#endif
						return false; // a flag to continue graph traversal
					}
					else // v.id == iter_fac->second.get<VE_ID>(), f.ve(v)->f.vs
					{
						(*ptr_loc_edges_hash_map)[std::pair<int, int>(v.id, iter_fac->second.get<VS_ID>())] =
							boost::make_tuple(prob, v.dist, v.dist + iter_fac->second.get<VE_DIST>() + iter_fac->second.get<VS_DIST>(), iter_fac->second.get<VS_ID>());
#ifdef ALGO_TESTING
						algo_out_file << ss_vs_ve.str() << ", d(r,vs) = " << v.dist << ", d(r,vs)+d(vs,ve) = " << v.dist + iter_fac->second.get<VE_DIST>() + iter_fac->second.get<VS_DIST>() << '\n';
#endif
						return false; // a flag to continue graph traversal
					}
				}
			}
		}
		else // v.type == 'r'
		{
			if (e.dist == 0) // v(r) overlaps e.ve, whatever e.ve.type is 'v' or 'f', no need to consider the virtual edge
				return false; // a flag to continue graph traversal
			else // e.dist != 0, v(r) must split an edge
			{
				if (e.ve.type != 'f') // e.ve is ordinary vertex
				{
					if (e.ve.id == ve_id) // r.vs->r.ve
					{
						(*ptr_loc_edges_hash_map)[std::pair<int, int>(vs_id, ve_id)] = boost::make_tuple(prob, 0.0f, e.dist, ve_id);
#ifdef ALGO_TESTING
						algo_out_file << ss_vs_ve.str() << ", d(r,vs) = " << 0 << ", d(r,vs)+d(vs,ve) = " << e.dist << '\n';
#endif
						return false; // a flag to continue graph traversal
					}
					else // e.ve.id == vs_id, r.ve->r.vs
					{
						(*ptr_loc_edges_hash_map)[std::pair<int, int>(ve_id, vs_id)] = boost::make_tuple(prob, 0.0f, e.dist, vs_id);
#ifdef ALGO_TESTING
						algo_out_file << ss_vs_ve.str() << ", d(r,vs) = " << 0 << ", d(r,vs)+d(vs,ve) = " << e.dist << '\n';
#endif
						return false; // a flag to continue graph traversal
					}
				}
				else // e.ve.type == 'f', r and f locate on and split the same edge
				{
					fac_hash_map::iterator iter_fac = ptr_fac_hash_map->find(e.ve.id); // the facility must exist
					if (iter_fac->second.get<VS_ID>() == vs_id)
					{
						if (iter_fac->second.get<VS_DIST>() < dist_vs) // v(r).ve->v(r).vs
						{
							(*ptr_loc_edges_hash_map)[std::pair<int, int>(ve_id, vs_id)] = boost::make_tuple(prob, 0.0f, dist_vs, vs_id);
#ifdef ALGO_TESTING
							algo_out_file << ss_vs_ve.str() << ", d(r,vs) = " << 0 << ", d(r,vs)+d(vs,ve) = " << dist_vs << '\n';
#endif
							return false; // a flag to continue graph traversal
						}
						else // iter_fac->second.get<VS_DIST>() > dist_vs (== never holds), v(r).vs->v(r).ve
						{
							(*ptr_loc_edges_hash_map)[std::pair<int, int>(vs_id, ve_id)] = boost::make_tuple(prob, 0.0f, dist_ve, ve_id);
#ifdef ALGO_TESTING
							algo_out_file << ss_vs_ve.str() << ", d(r,vs) = " << 0 << ", d(r,vs)+d(vs,ve) = " << dist_ve << '\n';
#endif
							return false; // a flag to continue graph traversal
						}
					}
					else // iter_fac->second.get<VS_ID>() == ve_id
					{
						if (iter_fac->second.get<VS_DIST>() < dist_ve) // v(r).vs->v(r).ve
						{
							(*ptr_loc_edges_hash_map)[std::pair<int, int>(vs_id, ve_id)] = boost::make_tuple(prob, 0.0f, dist_ve, ve_id);
#ifdef ALGO_TESTING
							algo_out_file << ss_vs_ve.str() << ", d(r,vs) = " << 0 << ", d(r,vs)+d(vs,ve) = " << dist_ve << '\n';
#endif
							return false; // a flag to continue graph traversal
						}
						else // iter_fac->second.get<VS_DIST>() > dist_ve (== never holds), v(r).ve->v(r).vs
						{
							(*ptr_loc_edges_hash_map)[std::pair<int, int>(ve_id, vs_id)] = boost::make_tuple(prob, 0.0f, dist_vs, vs_id);
#ifdef ALGO_TESTING
							algo_out_file << ss_vs_ve.str() << ", d(r,vs) = " << 0 << ", d(r,vs)+d(vs,ve) = " << dist_vs << '\n';
#endif
							return false; // a flag to continue graph traversal
						}
					}
				}
			}
		}
	}

	void set_data_structure(fac_hash_map *fac_hash_map_in, loc_edges_hash_map *loc_edges_hash_map_in)
		{ ptr_fac_hash_map = fac_hash_map_in; ptr_loc_edges_hash_map = loc_edges_hash_map_in; }
	void set_vs_ve(int vs_in, int ve_in, double dist_vs_in, double dist_ve_in) { vs_id = vs_in; ve_id = ve_in; dist_vs = dist_vs_in; dist_ve = dist_ve_in; }
	void set_prob(double prob_in) { prob = prob_in; }

private:
	fac_hash_map *ptr_fac_hash_map; // a pointer to a hash map of facilities associated with endpoints
	loc_edges_hash_map *ptr_loc_edges_hash_map; // a pointer to an assistant hash map for local network edges
	int vs_id, ve_id; // the original starting and ending ordinary vertices of the edge which the reference location splits
	double dist_vs, dist_ve; // the distances from reference location to vs and ve
	double prob; // present probability of the reference location
};

/*********************重载的多个 LNB 构造函数*********************/
void LNB_construct_LNT(bool is_to_bidirectional, const char* edges_file_path, const char* facs_file_path, const char* reflocs_file_path,
	LNT_hash_map& LNT, vertex_nnd_hash_map& nnd_map, typed_directed_graph& graph, fac_hash_map& facs_map);
void LNB_construct_LNT(bool is_to_bidirectional, const char* edges_file_path, const char* facs_file_path, const char* reflocs_file_path, LNT_hash_map& LNT, vertex_nnd_hash_map& nnd_map, typed_directed_graph& graph, fac_hash_map& facs_map, std::map<int, std::set<std::pair<int, int>>>& refloc_LN_map, std::map<int, std::pair<int, double>>& refloc_info_map);
void LNB_construct_LNT(bool is_to_bidirectional, const char* edges_file_path,const wh::facility_info_map & facility_info,const wh::reference_info_list &refloc_info , LNT_hash_map& LNT, vertex_nnd_hash_map& nnd_map, typed_directed_graph& graph, fac_hash_map& facs_map, std::map<int, std::set<std::pair<int, int>>>& refloc_LN_map, std::map<int, std::pair<int, double>>& refloc_info_map);


/*********************重载的多个 LNB 查询函数*********************/
candidate LNB_query(int& checked_num, LNT_hash_map& LNT, const vertex_nnd_hash_map& nnd_map, const typed_directed_graph& graph,
	const fac_hash_map& facs_map, const char* cands_file_path);
candidate LNB_query(int& checked_num, LNT_hash_map& LNT, const vertex_nnd_hash_map& nnd_map, const typed_directed_graph& graph,
	const fac_hash_map& facs_map, const char* cands_file_path, std::map<int, std::tuple<int, int, double, double>>& cands_map);
candidate LNB_query(int& checked_num, LNT_hash_map& LNT, const vertex_nnd_hash_map& nnd_map, const typed_directed_graph& graph,
	const fac_hash_map& facs_map, wh::candidate_info_map& candidate_info);


/********************* LNB 更新函数*********************/
void LNB_update_LNT(const candidate& ol, LNT_hash_map& LNT, typed_directed_graph& graph, fac_hash_map& facs_map, std::map<int, std::set<std::pair<int, int>>>& refloc_LN_map, wh::candidate_info_map& cands_map, const char* reflocs_file_path, std::map<int, std::pair<int, double>>& refloc_info_map);


/********************* greedy_LNB 函数 *********************/
void greedy_LNB(wh::facility_info_map& facility_info, wh::candidate_info_map& candidate_info, wh::reference_info_list& refloc_info, wh::Config& config);

#endif
